#include "../include/steiner.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void insert_presents(int * values, int * tam, int dado) {
  int i,j;
  if ((*tam) == 0) {
    values[0] = dado;
    (*tam)++;
  } else {
    for (i=0;i<(*tam);i++) {
      if (values[i] >= dado) {
	break;
      };
    };
    if (i >= (*tam)) {
      values[i] = dado;
      (*tam)++;
    } else if (values[i] != dado) {
      for (j=((*tam));j>i;j--) {
	values[j] = values[j-1];
      };
      values[i] = dado;
      (*tam)++;
    };
  };
  return (void) 0;
};

void reconstruct_path(int a, int b, int * local, int ** pred, int * tam) {
  if (pred[a][b] != a) {
    reconstruct_path(a,pred[a][b],local,pred,tam);
    reconstruct_path(pred[a][b],b,local,pred,tam);
  } else {
    insert_presents(local,tam,a);
    insert_presents(local,tam,b);
  };
  return (void) 0;
};


/* Funcao que resolve aproximadamente o problema da arvore de steiner  *
 * minima por GRASP                                                    *
 * entrada: grafo e lista de vertices terminais                        *
 * saida: grafo (arvore de steiner minima)                             */
void GRASPsteiner(graph * g, int *lv, int numTerm) {

   int    custoTotal;
   int    i,j,k;
   graph  *G2;
   graph  mudado;
   graph  *saida;
   graph  *tree;
   graph  local;
   graph  *retorno;
   int    ** pred;
   int    * presents;
   int    tamPresents;
   int    * saindo;
   int    tamSaida;
   int    * res;
   int    tamres;
   int    custoact;

   presents = (int *) malloc(sizeof(int)*(g->TotalNodes));
   tamPresents = 0;
   
   res = (int *) malloc(sizeof(int)*(g->TotalNodes));
   tamres = 0;

   custoTotal = MAX_CST;

   G2 = (graph *) malloc(sizeof(graph));
   
   G2 = grafoDist(g, &mudado, lv, numTerm, &pred);

   initializeGraph(&local,g->TotalNodes);

   for(k=0;k<100;k++) {

     printf("%d%\n",k);
     
     tree = (graph *) malloc(sizeof(graph));
     primGraph(G2,tree);
     
     for (i=0;i<numTerm;i++) {
       for (j=0;j<numTerm;j++) {
	 if (tree->adjacency[i][j] >= 0) {
	   reconstruct_path(lv[i],lv[j],presents,pred,&tamPresents);
	 };
       };
     };

     freeGraph(tree);

     //     buscaLocal(retorno,&local);
     
     custoact = buscaLocal(&(saindo), presents, g, tamPresents, &(tamSaida), lv, numTerm);

     /* em seguida, aplicar busca local para aprimorar a solucao G2 */
     
     if (custoTotal >= 0) {
       if (custoact >= 0) {
	 if (custoact < custoTotal) { /* atualiza solucao */
	   custoTotal = custoact;
	   memcpy(res,saindo,tamSaida*sizeof(int));
	   tamres = tamSaida;
	 };
       };
     } else {
       custoTotal = custoact;
       memcpy(res,saindo,tamSaida*sizeof(int));
       tamres = tamSaida;
     };

     free(saindo);
     
   };   

   printf("%d\n",custoTotal);
   
   return (void) 0;
   
};
